# coding: utf-8
# LRU（最近最少使用）缓存实现，核心操作get(找到后移到头部)、set(插入到头部，超过容量的话删除尾部)
# 实现1：dict（存key和value）+dict（存访问频率）
# 实现2：OrderedDict(会按元素第一次插入的顺序)
# https://www.kunxi.org/2014/05/lru-cache-in-python/
# https://www.cnblogs.com/ajianbeyourself/p/4555560.html

import collections

class LRUCache1(object):
    def __init__(self,capacity):
        #容量
        self.capacity=capacity
        #访问次数(一直递增)
        self.times=0
        #缓存
        self.cache={}
        #记录访问频率
        self.lru={}
    def __repr__(self):
        return "LRUCache1 capacity({0}) times({1}) cache({2}) lru({3})".format(self.capacity, self.times, self.cache, self.lru)
    def get(self,key):
        if key in self.cache:
            self.lru[key]=self.times
            self.times+=1
            return self.cache[key]
        return -1
    def set(self,key,value):
        #如果空间不够，删除最老的对象
        if len(self.cache)>=self.capacity:
            #min(迭代对象, key=最大值求法)
            oldKey=min(self.lru.keys(), key=lambda k:self.lru[k])
            self.cache.pop(oldKey)
            self.lru.pop(oldKey)
        #新来的永远是最新的
        self.cache[key]=value
        self.lru[key]=self.times
        self.times+=1

class LRUCache2:
    def __init__(self,capacity):
        self.capacity=capacity
        self.cache=collections.OrderedDict()
    def __repr__(self):
        return "LRUCache2 capacity({0}) cache({1})".format(self.capacity, self.cache)
    def get(self,key):
        try:
            val=self.cache.pop(key)
            self.cache[key]=val
            return val
        except KeyError:
            return -1
    def set(self,key,newVal):
        try:
            val=self.cache.pop(key)
        except KeyError:
            if len(self.cache)>=self.capacity:
                #last=False => not LIFO, but FIFO
                self.cache.popitem(last=False)
        self.cache[key]=newVal

#链表实现见single_linkedlist.py

lru1=LRUCache1(5)
lru1.set("10","tom")
lru1.set("11","tom1")
lru1.set("12","tom2")
lru1.set("13","tom3")
lru1.set("14","tom4")
lru1.get("10")
lru1.set("15","tom5")
lru1.set("16","mary")
print(lru1)

